package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/11.
 *
 * 给定一个有序数组，如{1,2,3,4,5,6,7,8,9}，我们将对这个数组进行选择，位置旋转未知。
 * 下面给出一个可能的旋转结果。如{4,5,6,7,8,9,1,2,3}，我们可以理解为它从元素4位置开始旋转。
 * 之后给定一个指定的数字n，让我们从{4,5,6,7,8,9,1,2,3}这个数组中找出它的位置，要求时间复杂度尽可能的低。
 */
public class RotateArray {

    public static int search(int[] arr, int k){
        int low = 0;
        int high = arr.length - 1;
        while (low < high){
            int middle = (low + high) / 2;
            if (middle == k) return middle;
            /**
             * arr[middle] > arr[low] 代表左边数组有序，则在左侧进行二分法查找
             * 否则 代表右边数组有序,则在右侧进行二分法查找
             * */
            if (arr[middle] > arr[low]){ //左边数组是有序的
                if (k <= arr[middle] && k >= arr[low] ){
                    // k 在中点的左边
                    high = middle -1;
                }else {
                    // k 在中点的右边
                    low = middle + 1;
                }
            }else {//右边数组是有序的
                if ( k >= arr[middle] && k <= arr[high]){
                    // k 在中点的右边
                    low = middle + 1;
                }else {
                    // k 在中点的左边
                    high = middle - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 顺序查找，耗时比较大
     * */
    public int search1(int[]arr, int k){
        int len = arr.length;
        for (int i = 0; i < len; i++){
            if (arr[i] == k) return i+1;
        }
        return -1;
    }
}
